Influence maximization (IM), which selects a set of $k$ users (called seeds)to maximize the influence spread over a social network, is a fundamentalproblem in a wide range of applications such as viral marketing and networkmonitoring. Existing IM solutions fail to consider the highly dynamic nature ofsocial influence, which results in either poor seed qualities or longprocessing time when the network evolves. To address this problem, we define anovel IM query named Stream Influence Maximization (SIM) on social streams.Technically, SIM adopts the sliding window model and maintains a set of $k$seeds with the largest influence value over the most recent social actions.Next, we propose the Influential Checkpoints (IC) framework to facilitatecontinuous SIM query processing. The IC framework creates a checkpoint for eachwindow slide and ensures an $\varepsilon$-approximate solution. To improve itsefficiency, we further devise a Sparse Influential Checkpoints (SIC) frameworkwhich selectively keeps $O(\frac{\log{N}}{\beta})$ checkpoints for a slidingwindow of size $N$ and maintains an$\frac{\varepsilon(1-\beta)}{2}$-approximate solution. Experimental results onboth real-world and synthetic datasets confirm the effectiveness and efficiencyof our proposed frameworks against the state-of-the-art IM approaches.
展开▼
机译：影响力最大化（IM）选择了一组$ k $用户（称为“种子”）以最大化在社交网络上传播的影响力，这是病毒式营销和网络监控等广泛应用中的一个基本问题。现有的IM解决方案无法考虑社会影响力的高度动态性，这会导致不良的种子质量或网络发展时的处理时间长。为了解决这个问题，我们在社交流上定义了一个名为IM的流IM查询。技术上，SIM采用滑动窗口模型并维护一组在最近的社交活动中影响力值最大的$ k $种子。接下来，我们提出了有影响力的检查点（IC）框架，以促进连续的SIM查询处理。 IC框架为每个窗口幻灯片创建一个检查点，并确保提供近似于\\ varepsilon $的解决方案。为了提高其效率，我们进一步设计了一个稀疏影响检查点（SIC）框架，该框架有选择地为大小为$ N $的滑动窗口保留$ O（\ frac {\ log {N}} {\ beta}）$检查点并保持$ \ frac {\ varepsilon（1- \ beta）} {2}-近似解。实际数据集和综合数据集上的实验结果证实了我们提出的框架针对最新的IM方法的有效性和效率。
展开▼
